/* graph.cpp
Desc.: Implementation of a simple undirected graph class (No error-checking for speed (for now))
Auth.: Ashwin Lall
Start: January 6, 2014
*/


#include "graph.h"
#include <fstream> 
#include <iostream>
using namespace std;

// constructor creates an initially empty graph
Graph::Graph()
{
    _numNodes = 0;
    _numEdges = 0;
}

// constructor for reading in a graph from the given file
// assumes that the edges are given in paired vertex format
// NOTE: Assumes that edges appear twice (once in either order)
Graph::Graph(string filename)
{
    _numNodes = 0;
    _numEdges = 0;
    this->readUndirectedGraph(filename);
}

// returns number of nodes
int Graph::numNodes()
{
    return _numNodes;
}

// returns number of edges
int Graph::numEdges()
{
    return _numEdges;
}

// return the set of nodes in the graph
set<int> Graph::getNodes()
{
    return _nodes;
}

// return a set of neighbors for 'node'
set<int> Graph::getNeighbors(int node)
{
    return _edges[node];
}

// return the degree for 'node'
int Graph::getDegree(int node)
{
    return _edges[node].size();
}

// adds a node to the graph if not already present
void Graph::addNode(int node)
{
    if (_nodes.count(node) == 0)
    {
	_nodes.insert(node);
	_numNodes++;
    }
}

// adds an edge to the graph
// if either node was not already in the graph, add it in
void Graph::addEdge(int node1, int node2)
{
    // don't double-add an edge
    if (hasEdge(node1, node2))
	return;

    if (_nodes.count(node1) == 0)
    {
	_nodes.insert(node1);
	_numNodes++;
    }
    if (_nodes.count(node2) == 0)
    {
        _nodes.insert(node2);
	_numNodes++;
    }

    _numEdges++;
    _edges[node1].insert(node2);
    _edges[node2].insert(node1);
}

// returns true if edge exists, false otherwise
bool Graph::hasEdge(int node1, int node2)
{
    return _edges[node1].count(node2) != 0;
}


// removes an edge from the graph
// does not remove node, even if it gets disconnected from rest of the graph
void Graph::removeEdge(int node1, int node2)
{
    _edges[node1].erase(node2);
    _edges[node2].erase(node1);
    _numEdges--;
}

// removes node and all edges associated with it
void Graph::removeNode(int node)
{
    set<int> nbrs = _edges[node];
    for (set<int>::iterator it = nbrs.begin(); it != nbrs.end(); ++it)
	removeEdge(node, *it);
    
    _nodes.erase(node);
    _numNodes--;
}


// removes all edges and nodes from the graph
void Graph::reset()
{
    //while (_nodes.size() > 0)
    //{ 
    //	removeNode(*_nodes.begin());
    //}

    _nodes.clear();
    _edges.clear();
	
    _numNodes = 0;
    _numEdges = 0;
}

// reads in a graph in paired vertex format
// discards any nodes and edges that were there before 
void Graph::readGraph(string filename)
{
    ifstream file;
    string line;
    int node1, node2, curr = 1;
    map<int, int> label;  // re-label the nodes 1,2,3,... in order of appearance
    bool directed = false;

    reset();

    file.open(filename.c_str());
    if (file.is_open())
    {
	while (getline(file, line))
	{
	    if (line[0] != '#')
	    {
		sscanf(line.c_str(), "%d %d", &node1, &node2);

		// re-lable nodes so that they are 1,2,3,....
		if (label.count(node1) == 0)
		{
		    label[node1] = curr;
		    curr++;
		}
		if (label.count(node2) == 0)
                {
                    label[node2] = curr;
                    curr++;
                }

		// insert labels (1,2,3,...) instead of actual node names
		if (!hasEdge(label[node1], label[node2]))
		    addEdge(label[node1], label[node2]);
	    }
	}
	file.close();
    }
}

// reads in a directed graph as an undirected graph; does not double add vertices
// discards any nodes and edges that were there before
void Graph::readUndirectedGraph(string filename)
{
    ifstream file;
    string line;
    int node1, node2, curr = 1;
    map<int, int> label;  // re-label the nodes 1,2,3,... in order of appearance
    bool directed = false;

    reset();

    file.open(filename.c_str());
    if (file.is_open())
    {
        while (getline(file, line))
        {
            if (line[0] != '#')
            {
                sscanf(line.c_str(), "%d %d", &node1, &node2);

                // re-lable nodes so that they are 1,2,3,....
                if (label.count(node1) == 0)
                {
                    label[node1] = curr;
                    curr++;
                }
                if (label.count(node2) == 0)
                {
                    label[node2] = curr;
                    curr++;
                }

                // insert labels (1,2,3,...) instead of actual node names
                if (node1 <= node2)  // makes sure that each edge only gets added once
                    addEdge(label[node1], label[node2]);
            }
        }
        file.close();
    }
}


void Graph::printGraph()
{
    for (set<int>::iterator n = _nodes.begin(); n != _nodes.end(); ++n)
    {
	int node = *n;
	set<int> nbrs = getNeighbors(node);
	cout << node << ":";
	for (set<int>::iterator nbr = nbrs.begin();  nbr != nbrs.end(); ++nbr)
	    cout << " " << *nbr;
	cout << endl;
    }
}
